A data packet traveling on communication networks carries in itself a network protocol stack comprising multiple protocol layers along with the packet data. The protocol layers help the network switches to classify and route the packet properly and efficiently from its sending device to its receiving device.
Traditionally, each network switch parses an incoming data packet to understand its packed protocol stack, then analyzes and processes each protocol layer in the packet serially. As transistor size has been scaled following the Moore's law, the underlining hardware in the network switches has become increasingly fast. As a result, the network switches are desired to be able to analyze multiple protocol layers of each packet in parallel in order to boost the network performance.
The network switches nowadays can check multiple fields in a packet in parallel for packet classification by checking several fields in the packet to see whether they match with some predefined values. Based on the matching results, the packet is classified to a specific flow for further processing. Furthermore, a network switch can also scan multiple fields in the packet simultaneously for efficient handling of quality of service and security for the packet.
In addition, the network switches can perform multiple lookups in parallel on different protocol layers of the packet in order to make a quick and proper routing decision. For a non-limiting example, a network switch can perform MPLS and bridge lookups on layer 2 and IP lookups on layer 3 simultaneously. In some cases, the network switch applies a prioritized decision policy to deal with the lookup results corresponding to these lookup queries so that the packet is forwarded to a correct output port. As networks are moving towards software-defined architectures with more new network protocols expected to be added to the networks, the network switches are desired to do more lookup operations in parallel per packet.
For performing multiple parallel lookups, a network lookup engine in the network switch needs to build multiple lookup keys for each packet and sends these lookup keys on parallel lookup queries to a remote/centralized search engine. For each received lookup key, the search engine will then search in its database for a lookup data and sends this lookup data on a lookup response back to the lookup engine sometime later.
A network switch normally includes several network lookup engines for different packet processing purposes but has only one (or a few) centralized search engine, which is shared by all these network lookup engines, because the search engine is very expensive in term of silicon area. The search engine can receive multiple lookup queries from these network lookup engines at the same time. As a result, lookup responses from the search engine arriving at each of the network lookup engines may not be in the same order as the packets in the flow processed by that network lookup engine. In addition, the parallel lookup queries of the same packet may be for different protocol layers, which require different searching latency. As a result, the parallel lookup queries may get the responses from the search engine at different times. The network lookup engine must guarantee correctly collection of these out-of-order responses for the lookup queries of the packets it is processing.
The foregoing examples of the related art and limitations related therewith are intended to be illustrative and not exclusive. Other limitations of the related art will become apparent upon a reading of the specification and a study of the drawings.